package com.solution.dichotomize;

import java.util.Arrays;

/*
    二分法
 */
public class Solution {

    public int findRadius(int[] houses, int[] heaters) {
        int res = 0;
        Arrays.sort(heaters);  // 此处不使用非稳定排序算法快排与稳定算法冒泡等，由于Arrays自带的排序方法已内部优化，会自动在局部选择最优排序
        for ( int house : houses ) {
            int i = binarySearch(heaters, house);
            int j = i + 1;
            int leftDistance = i < 0 ? Integer.MAX_VALUE : house - heaters[i];
            int rightDistance = j >= heaters.length ? Integer.MAX_VALUE : heaters[j] - house;
            int minDistance = min(leftDistance, rightDistance);  // 求出房子左边或右边能触及到取暖炉的最短位置
            res = max(res, minDistance);  // 对所有最短触及位置，取最长的
        }
        return res;
    }

    public int binarySearch(int[] heaters, int house) {
        int left = 0, right = heaters.length - 1;
        if ( heaters[left] > house )  // 最左边暖炉的位置（house.index + 1）大于房屋尺寸时
            return -1;
        while ( left < right ) {
            int mid = ( right - left + 1 ) / 2 + left;  // 此处会向下取整，如1.5取整得1
            if ( heaters[mid] > house )
                right = mid - 1;  // 如果房子距离暖炉仍然过远
            else
                left = mid;  // 房子可以触及到的且最近的暖炉
        }
        return left;
    }

    public int min(int a, int b) {
        return a > b ? b : a;
    }

    public int max(int a, int b) {
        return a > b ? a : b;
    }

}
